UVa/10149 - Yahtzee/10149.2.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <numeric>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 typedef int turn[5];
  28
  29 enum category {
  30   ones, twos, threes, fours, fives, sixes, chance, three_of_a_kind,
  31   four_of_a_kind, five_of_a_kind, short_straight, long_straight,
  32   full_house
  33 };
  34
  35 int score(turn t, int c){
  36   int times[7] = {0};
  37   for (int i=0; i<5; ++i) times[t[i]]++;
  38   switch(c){
  39   case ones:
  40   case twos:
  41   case threes:
  42   case fours:
  43   case fives:
  44   case sixes:
  45     return times[c+1] * (c+1);
  46   case chance:
  47     return accumulate(t, t+5, 0);
  48   case three_of_a_kind:
  49     for (int i=1; i<=6; ++i) if (times[i] >= 3) return accumulate(t, t+5, 0);
  50     return 0;
  51   case four_of_a_kind:
  52     for (int i=1; i<=6; ++i) if (times[i] >= 4) return accumulate(t, t+5, 0);
  53     return 0;
  54   case five_of_a_kind:
  55     for (int i=1; i<=6; ++i) if (times[i] >= 5) return 50;
  56     return 0;
  57   case short_straight:
  58     for (int i=1; i<=3; ++i)
  59       if (times[i] > 0  && times[i+1] > 0 && times[i+2] > 0 && times[i+3] > 0) return 25;
  60     return 0;
  61   case long_straight:
  62     for (int i=1; i<=2; ++i)
  63       if (times[i] > 0  && times[i+1] > 0 && times[i+2] > 0 && times[i+3] > 0 && times[i+4] > 0) return 35;
  64     return 0;
  65
  66   case full_house:
  67     for (int i=1; i<=6; ++i)
  68       for (int j=1; j<=6; ++j)
  69         if (times[i] == 3 && times[j] == 2) return 40;
  70     return 0;
  71   default:
  72     printf("Something very bad happened.\n");
  73   }
  74   return 0;
  75 }
  76
  77 turn turns[13];
  78
  79 int dp[13][1 << 13];
  80 /*
  81   dp[i][mask] = Best score having matched categories [0..i] and turns <on> on mask.
  82  */
  83 int choice[13][1 << 13];
  84
  85 int main(){
  86   while (true){
  87     for (int i=0; i<13; ++i){
  88       for (int j=0; j<5; ++j){
  89         if (scanf("%d", &turns[i][j]) != 1) return 0;
  90       }
  91     }
  92
  93     for (int i=0; i<13; ++i)
  94       for (int j=0; j<(1 << 13); ++j)
  95         dp[i][j] = INT_MIN, choice[i][j] = -1;
  96
  97
  98     //First category
  99     for (int t=0; t<13; ++t){
 100       dp[ones][1 << t] = score(turns[t], ones);
 101       choice[ones][1 << t] = t;
 102     }
 103     //Let's dance!
 104     for (int c=twos; c<=full_house; ++c){
 105       for (int mask = 0; mask < (1 << 13); ++mask){
 106         if (__builtin_popcount(mask) != c + 1) continue;
 107         for (int t=0; t<13; ++t){
 108           int prev_mask = mask & ~(1 << t);
 109
 110           int canDo = dp[c-1][prev_mask] + score(turns[t], c);
 111           if (canDo > dp[c][mask]){
 112             dp[c][mask] = canDo;
 113             choice[c][mask] = t;
 114           }
 115         }
 116         if (c == sixes && dp[c][mask] >= 63){
 117           //Add bonus
 118           dp[c][mask] += 35;
 119         }
 120       }
 121     }
 122
 123     //Now find the matching from the computed table
 124     //The last state is dp[all_categories][all_turns] = dp[12][11111...1111B]
 125     int match[13];
 126     for (int c=12, mask = (1 << 13) - 1; c >= 0; c--){
 127       match[c] = choice[c][mask];
 128       mask &= ~(1 << choice[c][mask]);
 129     }
 130     int sum = 0, bonus = 0;
 131     for (int c = ones; c <= full_house; ++c){
 132       int s = score(turns[match[c]], c);
 133       printf("%d ", s);
 134       sum += s;
 135       if (c == sixes && sum >= 63){
 136         sum += (bonus = 35);
 137       }
 138
 139     }
 140     //assert(sum == dp[12][(1 << 13) - 1]);
 141     printf("%d %d\n", bonus, sum);
 142   }
 143   return 0;
 144 }